Ćwiczenia/2. Ćwiczenia/Zadanie 2 (liczba inwersji tablicy).ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> Proszę zaproponować i zaimplementować algorytm, który mając na wejściu tablicę A zwraca liczbę jej inwersji (t.j., liczbę par indeksów i < j takich, że A[i] > A[j]."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Do zaimplementowania zliczania inwersji, najlepiej wykorzystać algorytm sortowania Merge Sort. Pozwala on znacznie zmniejszyć złożoność obliczeniową z algorytmu brute force, który porównuje wszystkie możliwe pary liczb ($ O(n^2)) $ do złożoności  $O(n \\cdot log(n)) $. Ponieważ, dzięki algorytmowi sortowania Merge Sort, mamy pewność, że za każdym razem wszystkie wartości w obu częściach tablicy (lewej oraz prawej) są posortowane w porządku niemalejącym, jeżeli, podczas łączenia tych części w jedną posortowaną tablicę (listę), znajdzie się wartość w lewej części, która jest większa od pewnej wartości w prawej części, wiemy, że ta wartość znajduje się na złym miejscu, więc przed nią nalezy umieścić bieżącą wartość z prawej tablicy. Jest to równoznaczne z tym, że bieżąca wartośc z prawej części tablicy jest w inwersji z każdą wartością z lewej tablicy, począwszy od tej, z którą została ostatnio porównana (bo ona, jak i kolejne wartości, są wówczas większe niż bieżąca wartość z prawej części tablicy)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Implementacja algorytmu"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "def count_inversions(arr, *, sort_=False):\n",
    "    # If we don't want array to be sorted, create a copy of it\n",
    "    if not sort_: arr = arr[:]\n",
    "    return _count_inversions(arr, 0, len(arr))\n",
    "    \n",
    "\n",
    "def _count_inversions(arr, left_idx, right_idx):\n",
    "    total = 0\n",
    "    # If there are at lest 2 elements in the current part, we can count inversions\n",
    "    if right_idx - left_idx >= 2:\n",
    "        mid_idx = (left_idx + right_idx) // 2\n",
    "        # Recursively add inversions counted in the left and the right part\n",
    "        # of the current part\n",
    "        total += _count_inversions(arr, left_idx, mid_idx)\n",
    "        total += _count_inversions(arr, mid_idx, right_idx)\n",
    "        # Add inversions that were counted in the current part\n",
    "        total += _count_merge_inversions(arr, left_idx, mid_idx, right_idx)\n",
    "        \n",
    "    return total\n",
    "\n",
    "\n",
    "def _count_merge_inversions(arr, i, j, end_idx):\n",
    "    begin_idx = i\n",
    "    mid_idx = j\n",
    "    merged = []\n",
    "    total = 0\n",
    "    \n",
    "    while i < mid_idx and j < end_idx:\n",
    "        if arr[i] > arr[j]:\n",
    "            total += mid_idx - i\n",
    "            merged.append(arr[j])\n",
    "            j += 1\n",
    "        else:\n",
    "            merged.append(arr[i])\n",
    "            i += 1\n",
    "            \n",
    "    # If there are still some values remaining, append them to the merged list\n",
    "    for i in range(i, mid_idx):\n",
    "        merged.append(arr[i])\n",
    "    for j in range(j, end_idx):\n",
    "        merged.append(arr[j])\n",
    "    \n",
    "    # Upsate the values in the array that is being sorted\n",
    "    idx = begin_idx\n",
    "    for val in merged:\n",
    "        arr[idx] = val\n",
    "        idx += 1\n",
    "        \n",
    "    return total"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "###### Kilka testów"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "22\n",
      "[7, 5, 2, 8, 3, 4, 1, 2, 5]\n",
      "22\n",
      "[1, 2, 2, 3, 4, 5, 5, 7, 8]\n"
     ]
    }
   ],
   "source": [
    "a = [7, 5, 2, 8, 3, 4, 1, 2, 5]\n",
    "print(count_inversions(a))\n",
    "print(a)\n",
    "\n",
    "print(count_inversions(a, sort_=True))\n",
    "print(a)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.10.0"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}